package bst;

public class BSTree {
    private TreeNode root;
    private int size;

    public BSTree() {
        this.root = null;
        this.size = 0;
    }

    // 查找的操作
    public boolean contains(long key) {
        TreeNode cur = root;

        while (cur != null) {
            if (key == cur.key) {
                return true;
            } else if (key < cur.key) {
                cur = cur.left;
            } else {
                // key > cur.key
                cur = cur.right;
            }
        }
        return false;
    }

    // 插入的操作
    // 插入过程中可能会失败（key 重复了）
    public boolean add(long key) {
        // 定义结点
        TreeNode node = new TreeNode(key);

        if (this.root == null) {
            this.root = node;
            this.size = 1;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = this.root;

        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                // key > cur.key
                parent = cur;
                cur = cur.right;
            }
        }

        // cur == null
        // 保证 parent 一定是 cur 的双亲
        // 断言 parent != null
        // 要做的工作，把 node 插入到 parent 的孩子中
        if (key < parent.key) {
            parent.left = node;
        } else {
            // key > parent.key
            parent.right = node;
        }

        this.size++;
        return true;
    }

    // 删除的操作
    public boolean remove(long key) {
        TreeNode parent = null;
        TreeNode cur = root;

        while (cur != null) {
            if (key == cur.key) {
                deleteNode(parent, cur);    // parent == null
                this.size--;
                return true;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                // key > cur.key
                parent = cur;
                cur = cur.right;
            }
        }
        return false;
    }

    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.left == null) {
            if (node == this.root) {    // parent == null
                this.root = node.right;
            } else if (parent.left == node) {
                parent.left = node.right;
            } else {
                // parent.right == node
                parent.right = node.right;
            }
        } else if(node.right == null) {
            if(node == this.root){
                this.root = node.left;
            }else if(parent.left == node){
                parent.left = node.left;
            }else{
                parent.right = node.left;
            }
        }else{
            //node.left != null && node.right != null
            //度为 2
            //利用替换删除的方式进行删除
            //选择左子树中最大的 或 右子树中最小的
            TreeNode toDeleteParent = node;
            TreeNode toDelete = node.right;
            //此处选择右子树中最小的一个
            //toDelete != null
            while(toDelete.left != null){
                toDeleteParent = toDelete;
                toDelete = toDelete.left;
            }
            //toDelete 是要删除的结点，交换 node 和 toDelete
            node.key = toDelete.key;
            //toDelete 的左孩子一定为 null ，如果不是 null 则说明 toDelete 不是右子树中最小的，上面的循环还应该继续
            //toDelete 可能是 toDeleteParent 的左孩子也可能是右孩子
            if(toDeleteParent.left == toDelete){
                toDeleteParent.left = toDelete.right;
            }else{
                toDeleteParent.right = toDelete.right;
            }
        }
    }

    public static void main(String[] args) {
        BSTree tree = new BSTree();
        long[] keys = { 5, 1, 6, 8, 3, 9, 0, 2, 4, 7 };
        for (long key : keys) {
            System.out.println(tree.add(key));
        }
    }
}
